1. Technical Field of the Invention
The present invention relates to compilers.
2. Background Art
A compiler is a program that reads a source program written in a source language and translates it into a target program in a target language. For example, a compiler may translate a high level source program (such as C++) into compiled code that can be understood by a processor, such as a microprocessor.
Block ordering (also called code placement) concerns the order in which instructions and blocks of instructions are to appear in physical memory. The block ordering may involve the selection of certain branch instructions between some of the blocks. It is generally true that it takes fewer cycles or other processor resources if the instruction is able to fall through to the next contiguous instruction in memory rather than branching to another instruction. Accordingly, block ordering involves attempting to pick the direction of a conditional branch such that it falls through to an instruction that is more likely to occur and branches to an instruction less likely to occur. Another benefit of doing so is that spatial locality is more likely to exist in a cache. Instruction scheduling involves moving instructions (called code motion) to better assign instructions to an execution unit for a particular cycle. The scheduler may move code within a block (called local code motion) or between blocks (called global code motion). Some schedulers are capable of only local code motion, while other schedulers are capable of local and global code motion.
In prior art compilers, block ordering and instruction scheduling are independent activities. For example, in the compiling process of some prior art compilers, first an instruction order and accordingly a block order is chosen. Next, instruction scheduling is performed. Instruction scheduling involves code motion or moving instructions to different locations in physical memory to attempt better utilization of execution units. If there are three execution units, an attempt is made to have each execution unit be busy during each cycle. Following the completion of scheduling, the physical order is re-evaluated to see if can be improved. For example, if an unconditional branch branches to the next sequential instruction in memory, the unconditional branch can be removed without changing the operation of the program. However, in making these changes to the physical order, the execution units may be less well utilized. Good block ordering increases performance. Good instruction scheduling also increases performance. In the prior art compilers, however, by treating instruction scheduling and ordering as sequential, independent activities, both the instruction ordering and scheduling suffer. Accordingly, performance suffers.
Accordingly, there is a need for a compiler with improved instruction scheduling and ordering.
In some embodiments, the invention includes a method of compiling instructions of a program. The method includes receiving instructions for code motion and controlling the code motion while interacting with block ordering.
The code motion may be done as part of instruction scheduling. The scheduling may involve making an assessment of the cost of scheduling an instruction and determining whether to make the code motion based on the cost.
The scheduling may involve regeneration of predicate expressions to invert conditional branches.